1. Technology Field
The present invention generally relates to a data writing method, in particular, to a data writing method for a flash memory and a controller using the same.
2. Description of Related Art
Along with the widespread of digital cameras, camera phones, and MP3 in recently years, the consumers' demand to storage media has increased drastically too. Flash memory is one of the most adaptable memories for such battery-powered portable products due to its characteristics such as data non-volatility, low power consumption, small volume, and non-mechanical structure. Besides being applied in foregoing portable products, flash memory is also broadly applied to external products such as flash cards and flash drives. Thereby, flash memory has become one of the most focused electronic products in recent years.
Flash memories can be categorized into single level cell (SLC) NAND flash memories and multi level cell (MLC) NAND flash memories according to the memory cells thereof. A flash memory is usually divided into a plurality of physical blocks, and for the convenience of description, these physical blocks will be referred as blocks thereinafter. Generally speaking, data in a flash memory is erased in unit of blocks, namely, each block contains the smallest number of memory cells which are erased together. Each block is usually divided into a plurality of pages. Page is usually the smallest programming unit, namely, page is the smallest unit for writing or reading data. However, it has to be noted that the smallest programming unit may also be a sector, namely, a page is further divided into a plurality of sectors and each sector is used as the smallest programming unit, in another flash memory design, such as a SLC NAND flash memory having the number of program (NOP) as 4.
FIGS. 1A˜1E are detailed block diagrams illustrating a flash memory 100 and the operation thereof according to a conventional technique.
FIG. 1A illustrates the general structure and operation of a flash memory. Referring to FIG. 1A, in order to program (i.e. write and erase) a flash memory 100 efficiently, blocks in the flash memory 100 are logically grouped into system blocks 102, data blocks 104, and spare blocks 106.
The system blocks 102 are used for recording system data, wherein the system data may be the number of zones in the flash memory 100, the number of blocks in each zone, the number of pages in each block, and a logical-physical mapping table of the flash memory 100. Generally speaking, more than 90% of blocks in the flash memory 100 are the data blocks 104.
The data blocks 104 are used for storing user data and which are usually the blocks corresponding to the logical block addresses (LBAs) operated by a host (not shown).
The spare blocks 106 are used for substituting the data blocks 104. Accordingly, the spare blocks 106 are blank blocks, namely, no data is recorded in these blocks or data recorded in these blocks is marked as invalid data. To be specific, an erase operation has to be performed before data is written to a position which already contains data. As described above, data is written into a flash memory in unit of pages while erased from the same in unit of blocks. Since an erase unit is larger than a write unit, those valid pages in a block have to be copied to another block before data is erased from this block. Accordingly, to write a new data into a block M which already contains data among the data blocks 104, a block S is first selected from the spare blocks 106, and the valid data in the block M is copied to the block S together with the new data. After that, the block M is erased and linked as a spare block 106, and at the same time, the block S is linked as a data block 104 (as shown in FIG. 1A).
Generally speaking, blocks in the flash memory 100 are further logically grouped into substitute blocks 108 in order to use the flash memory 100 more efficiently.
FIG. 1B illustrates another operation of a flash memory, and FIG. 1C is a detailed diagram of the operation in FIG. 1B.
Referring to FIG. 1B and FIG. 1C, the substitute blocks 108 are used for substituting the data blocks 104. To be specific, when a block C is selected from the spare blocks 106 for substituting the block M among the data blocks 104, a new data is written into the block C but the valid data in the block M is not instantly copied into the block C to erase the block M. Instead, the valid data before the writing address in the block M (i.e., pages P0 and P1) is copied to the block C (as shown in (a) of FIG. 1C), and the new data (i.e., pages P2 and P3 in the block C) is written into the block C (as shown in (b) of FIG. 1C). Here the block C containing part of the old valid data and the new data is temporarily linked as a substitute block 108. This is because the valid data in the block M may become invalid in the next operation, so that instantly moving all the valid data in the block M to the block C may become meaningless. In the present example, the fact that multiple physical block addresses (PBAs) are mapped to one LBA is recorded, namely, the content of the block M and the content of the block C together is the content of a corresponding logical block. The blocks M and C are merged only when the contents thereof are actually to be combined, so that the usage efficiency of these blocks can be improved. For example, as shown in (c) of FIG. 1C, when foregoing two blocks are merged, the remaining valid data in the block M (i.e., pages P4˜PN) is copied to the block C, then the block M is erased and linked as a spare block 106, and at the same time, the block C is linked as a data block 104.
In the example described above, the updated data when the two blocks are merged occupies exactly an entire page, and accordingly, the remaining valid data in the block M can be directly written into a page right after the updated data in the block C. However, the updated data may also occupy only part of a page. FIG. 1D illustrates another operation of the flash memory, and FIG. 1E is a detailed diagram of the operation in FIG. 1D.
In the example illustrated in FIG. 1D and FIG. 1E, the remaining valid data in the block M does not occupy an entire page (i.e., part of the old data and part of the new data occupy the same page, as page P3 in FIG. 1E). Thus, when the two blocks are merged, a blank block S is first selected from the spare blocks 106, and the valid data in the block M and the block C is copied into the block S. After that, the block M and the block C are erased and linked as spare blocks 106, and the block S is linked as a data block 104, so as to complete the merge operation. The reason for selecting the block S to merge the blocks M and C is that since each page can only be programmed once (the page P3 in the block C has been programmed), a blank block (for example, the block S in FIG. 1C) has to be selected for writing the data completely.
If a MLC NAND flash memory is used, each page in the MLC NAND flash memory includes four sectors, namely, each page has four sectors of 512 bytes, which is totally 2K bytes, wherein a sector is the smallest storage unit used in a file system. As described above, data is written into a flash memory in unit of pages. Accordingly, four sectors have to be programmed together in a MLC NAND flash memory. In other words, in foregoing example illustrated in FIG. 1E, even though the new data is not enough for an entire page (for example, the page P3 in the block C), the page P3 in the block C still has to be programmed entirely. However, if a next writing command is received before the blocks are merged and the writing command instructs that the data to be updated is right after the previously updated data (i.e., follows the update data in the page P3 of the block C), since the page P3 in the block C has been programmed in step (c) of FIG. 1E, a blank block has to be selected for copying the data in the pages P0˜P2 of the block C again, and then the data in the page P3 of the block C is written together with the update data.
Due to the physical characteristics of a flash memory, a block has to be erased every time before a data is written into the block. However, the block may contain valid data originally. Thus, the valid data has to be moved (i.e., copied) before the block is erased. Foregoing operation for writing data of small quantity into the flash memory (as shown in FIG. 1E) may subsequently result in meaningless erasing and programming operations performed on the flash memory, and accordingly may reduce the efficiency of a storage device and the lifespan of the flash memory (i.e., only a limited number of erasing operations can be performed on the flash memory).